package likou.offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/8/20  20:55
 */
public class _37 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(2);
        root.right.right = new TreeNode(4);
        System.out.println(serialize(root));
    }

    public static String serialize(TreeNode root) {
        List<Integer> daan = new ArrayList<>();
        List<TreeNode> tempA = new ArrayList<>();
        List<TreeNode> tempB = new ArrayList<>();
        int i = 0;
        tempA.add(root);
        daan.add(root.val);
        int p = 0;
        while (tempA.size() != 0) {
            if (tempA.get(i) != null) {
                if (tempA.get(i).left != null) {
                    while (p != 0) {
                        daan.add(null);
                        p--;
                    }
                    daan.add(tempA.get(i).left.val);
                    tempB.add(tempA.get(i).left);
                } else {
                    p++;
                }
                if (tempA.get(i).right != null) {
                    while (p != 0) {
                        daan.add(null);
                        p--;
                    }
                    daan.add(tempA.get(i).right.val);
                    tempB.add(tempA.get(i).right);
                } else {
                    p++;
                }
            }
            i++;
            if (i == tempA.size()) {
                tempA = tempB;
                tempB = new ArrayList<>();
                i = 0;
            }
        }
        deserialize(daan.toString());
        return daan.toString();
    }

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        String one = data.split("\\[")[1];
        String two = one.split("\\]")[0];
        String[] ww2 = two.replaceAll(" ","").split(",");
        if (ww2.length == 0) {
            return null;
        }
        List<TreeNode> stepA = new ArrayList<>();
        List<TreeNode> stepB = new ArrayList<>();
        TreeNode root = new TreeNode(Integer.valueOf(ww2[0]));
        stepA.add(root);
        int index = 1;
        for (int i = 0; i < stepA.size(); i++) {
            if (index == ww2.length) {
                break;
            }
            if (index < ww2.length) {
                if (!"null".equals(ww2[index])) {
                    stepA.get(i).left = new TreeNode(Integer.valueOf(ww2[index]));
                    stepB.add(stepA.get(i).left);
                }
                index++;
            }
            if (index < ww2.length) {
                if (!"null".equals(ww2[index])) {
                    stepA.get(i).right = new TreeNode(Integer.valueOf(ww2[index]));
                    stepB.add(stepA.get(i).right);
                }
                index++;
            }
            if (i==stepA.size()-1&&stepB.size()!=0){
                stepA = stepB;
                i = -1;
                stepB = new ArrayList<>();
            }
        }
        System.out.println(root.val);
        return root;
    }
}
